package _6_旋转数组的最小数字;

/**
 * 题目描述
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 */

/**
 * 思路：利用二分的思想，如果中间的数大于数组末尾的数，
 * 说明左边是有序的，最小值肯定在右面或者mid，让start=mid
 * 否则在左面，让end=mid
 */
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0) return 0;
        int start=0,end=array.length-1;
        int mid = start+(end-start)/2;
        while(start<end-1){
            mid=start+(end-start)/2;
            if(array[mid]>array[end]){
                start=mid;
            }
            else{
                end=mid;
            }

        }
        return Math.min(array[start],array[end]);
    }

    /**
     *  2 3 4 5 6 1
     *  当start<=end时候：
     *     start end    mid
     *     0      5      2
     *     3      5      4
     *     5      5      5
     *     5      5      5（陷入循环）
     *
     */
    public int minNumberInRotateArray2(int [] array) {
        if(array.length==0) return 0;
        int start=0,end=array.length-1;
        int mid = start+(end-start)/2;
        while(start<end){
            mid=start+(end-start)/2;
            if(array[mid]>array[end]){
                start=mid+1;
            }
            else{
                end=mid;
            }

        }
        return array[start];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minNumberInRotateArray2(new int[]{5,1,2,3,4}));
    }
}
